1. Field of the Invention
The present invention relates to a two-dimensional bar code reading method, a data storage medium carrying a computer program product embodying the method, and two-dimensional bar code reading apparatus. More particularly, the present invention relates to a two-dimensional bar code reading method, data storage medium, and two-dimensional bar code reading apparatus for locating the finder pattern in an image captured by scanning a two-dimensional code symbol, locating the direction module, locating the data module, and converting the data module to data characters.
2. Description of Related Art
Bar codes are a type of automated recognition technology that developed in the retail industry as a way to look up information in a database about an item quickly and accurately. Bar codes have since evolved and found application in such diverse industries as warehousing and distribution, government, medicine, research, and event management. As bar codes and their applications have become more varied, demand for bar codes has spread to industries and applications for which traditional bar codes are ill-suited, including bar code miniaturization for imprinting on very small items and high coding capacity. Two-dimensional bar codes addressing these needs have been developed in recent years.
There are two types of two-dimensional bar codes: stacked symbology (or multi-row codes), and matrix codes. Stacked symbologies comprise multiple rows of one-dimensional bar codes stacked in a vertical alignment. Stacked symbologies can be read using a laser scanner, CCD scanner, or other scanning method. Matrix codes encode data using black and white data cells arranged in a pattern determined by the particular code protocol. Matrix codes can be read using a CCD image reader or other image sensing method.
One type of matrix code is called MaxiCode. MaxiCode was designed for sorting and tracking package shipments. Package delivery services in the United States use MaxiCode in their collection and distribution centers for shorting shipments by destination and for ship loading. The two-dimensional (2D) symbol generated and displayed according to the MaxiCode standard is referred to below as the MaxiCode symbol.
A typical MaxiCode symbol is shown in FIG. 59. FIG. 59(a) shows a complete MaxiCode symbol, and FIG. 59(b) shows the finder pattern and orientation module of the MaxiCode symbol.
As shown in FIG. 59(a), a finder pattern 5901 is positioned at the center of every MaxiCode symbol 5900. Every finder pattern 5901 comprises six concentric parts, including a white center circle, two white rings, and three black rings. The finder pattern 5901 is used to locate and isolate the MaxiCode symbol 5900 from the captured image. The center of the MaxiCode symbol is identified by locating the center of the finder pattern 5901.
The space within the MaxiCode symbol around the finder pattern 5901 is populated by module groups consisting in total of 884 black or white interlocking modules 5902. Each module 5902 is a regular hexagon. The module groups consist of six orientation module groups 5903 and a data module group. Each orientation module group consists of the 3 orientation modules indicating the orientation of the MaxiCode symbol 5900. The data module group consists of the 864 data modules representing the encoded data; one data module corresponds to one data bit. Data modules are used for encoding data, and are used for error correction processing. Note that the two modules at the top right of the symbol are not used.
As shown in FIG. 59(b), the regular hexagon module 5902 is sized so that it is internally tangent to the white center bullseye of the finder pattern 5901. The orientation module groups 5903 define a virtual regular hexagon of which the center is the center point 0 of the finder pattern 5901. Each orientation module group 5903 includes an inside orientation module 5904, outside orientation module 5905, and center orientation module 5906. The six orientation module groups 5903 thus comprise a total 18 orientation modules. Finding these 18 orientation modules identifies the orientation of the MaxiCode symbol and enables the data to be read from the data modules.
It should be noted here that in each orientation module group 5903 the inside orientation module 5904 is the one located at the shortest distance from the center point 0, the outside orientation module 5905 is the one located at the farthest distance from the center point 0, and the center orientation module 5906 is the one located at a distance from the center point 0 that is between the distance from center point 0 to the inside orientation module 5904 and the distance from center point 0 to the outside orientation module 5905.
An image sensing technique is used to read MaxiCode symbols, which as noted above are a type of two-dimensional code symbology. In other words, a MaxiCode symbol is captured as image data which is then interpreted (decoded). This operation is described more fully below.
The first step is to find the MaxiCode symbol finder pattern and orientation modules in the captured image, and then recognize the data modules. A bit pattern is then generated from the data modules, assigning a bit value of 1 to each dark (typically black) data module, and 0 to each light (typically white) data module. The resulting bit pattern is then converted to corresponding data characters to decode the data in the MaxiCode symbol. Various methods have been developed for decoding the scanned image of a MaxiCode symbol.
It is always necessary to find the center of the finder pattern to decode a MaxiCode to symbol. JP-A-10-21322 teaches one method for finding the center of the finder pattern.
This method first finds all Jordan curves having an angular distance between two points less than xcexa3; then, finds all convex Jordan curves within the found Jordan curves; determines the equations of a pair of tangents from the end points of each convex Jordan curve; determines the equations of the center lines for each pair of tangents; determines the point of intersection of the center lines; and thus finds the center point of the finder pattern based on the intersection of the center lines. Decoding the MaxiCode symbol then proceeds.
A problem with the method taught in JP-A-10-21322 is that processing is time-consuming because of the steps needed to isolate all convex Jordan curves from among all Jordan curves found, then determine the equations of the tangents, and finally look for the center of the finder pattern of the symbol.
A method using templates to find the center of the finder pattern is taught in WO95/34043. However, WO95/34043 simply says that the six symbol axes, which are offset 60 degrees each, pass through the center of the bull""s-eye, and that the center of the template is overlaid to the center of the bull""s-eye. It says nothing specific about how to overlay the template with the center of the bull""s-eye.
Finding the orientation modules is also important, and various methods of accomplishing this have been proposed. Finding the orientation modules is essentially finding the location and shape of the orientation modules. By finding the location and shape of the orientation modules it is not only possible to detect the location of each data module based on the dimensions of a MaxiCode symbol module, it is also possible to identify the color, that is, the bit value, of the detected data modules.
FIG. 60 shows module groups in a MaxiCode symbol. As shown in FIG. 60, module group 6000 comprises orientation module groups 6001a, 6001b, 6001c, 6001d, 6001e, 6001f, each containing plural orientation modules as noted above, and data module group 6002 comprising the individual data modules. Note, further, that the bit pattern (where black=1 and white=0) of the three orientation modules constituting each of the six orientation module groups 6001a, 6001b, 6001c, 6001d, 6001e, 6001f differs according to the orientation. Various methods have therefore been proposed for locating the orientation modules, but each of these methods requires a complex process. The orientation module location process is therefore time-consuming.
Various methods have also been proposed for detecting data module locations based on the found orientation modules, and converting the bit pattern corresponding to the colors of the detected modules to data characters in a single continuous process. These methods also necessitate a complex process, and are therefore also time-consuming.
The process for decoding the scanned MaxiCode symbol image can decode scanned images captured as direct frontal images. However, depending upon where on the packages to be stored the respective MaxiCode symbol is placed and the location of the two-dimensional bar code scanner, the MaxiCode symbol is not necessarily captured as a frontal view. In practice, it is commonly necessary to decode scanned images captured at an angle, but it is often not possible to decode such images.
FIG. 62 shows the relationship between an actual MaxiCode symbol and the captured scanned image of the MaxiCode symbol. FIG. 62(a) shows the relationship between a MaxiCode symbol scanned from the front and the resulting scanned image, and FIG. 62(b) shows the relationship between a MaxiCode symbol scanned from an angle and the resulting scanned image.
As shown in FIG. 62(a), the scanned image of a MaxiCode symbol scanned from the front and the actual MaxiCode symbol are similar. More specifically, the relative positions of the finder pattern and various modules in the scanned image of the MaxiCode symbol are the same as the relative positions of the finder pattern and modules in the actual MaxiCode symbol. The shapes of the finder pattern and modules in the scanned image are also similar to the finder pattern and modules in the actual MaxiCode symbol.
When the scanned image of a MaxiCode symbol captured from an angle is compared with the actual MaxiCode symbol, however, the relative positions of the finder pattern and modules in the scanned image are obviously different from the relative positions of the finder pattern and modules in the actual MaxiCode symbol as shown in FIG. 62(b). In addition, the shapes of the finder pattern and modules in the scanned image are not similar to the shape of the finder pattern and modules in the actual MaxiCode symbol, instead the scanned image is deformed. It is therefore generally difficult to recognize the position and colors of the data modules constituting the MaxiCode symbol.
Decoding scanned images of MaxiCode symbols, which is a typical two-dimensional bar code symbology, when the image is captured at an angle is thus subject to a high error rate, making it impossible in some cases to decode the MaxiCode symbol.
Resolving this problem has required a distortion correction operation to convert distorted scanned images to images with no distortion. A commonly used distortion correction method is normalization.
FIG. 63 is used below to describe distortion correction of an image using normalization. FIG. 63(a) shows two types of distortion, and FIG. 63(b) shows a scanned image decoding process using normalization.
As shown in FIG. 63(a), distorted images can have perspective distortion or rotational distortion. Both types can be corrected to distortion-free images through normalization. As shown in FIG. 63(b), a process for decoding a distorted scanned image first extracts the symbol image, then normalizes the extracted image, and finally decodes the distortion-corrected image to read the information encoded in the symbol.
As shown in FIG. 59 and described above, a MaxiCode symbol has the finder pattern located in the center thereof with all surrounding modules being regular hexagons. As a result, is it difficult to mathematically characterize the symbol shape when the border around the symbol or the data modules at the vertices are white. Normalization, which is a common distortion correction technique, cannot be used to accurately normalize a distorted MaxiCode symbol.
Furthermore, even if normalization can be successfully applied to correct distortion, the correction process is quite time-consuming.
The present invention is directed to a solution for the above problems. More specifically, it is the object of the present invention to provide a method and a reading apparatus that allow shortening the time required for decoding a scanned image of a two-dimensional code system, in particular a MaxiCode symbol.
This is accomplished by finding the center point of the MaxiCode symbol finder pattern using a method that is simple, fast, and does not impose a high processing burden on the computer; correcting the scanned image based on the relationship between the two-dimensional bar code symbol and the scanned image of the two-dimensional bar code symbol so that a decoding process can be applied to a scanned image captured from an angle; detecting pixel data matching a color template pattern based on pixel data in the orientation module search range of the scanned image of the two-dimensional bar code symbol; finding all orientation modules based on the detected pixel data; finding all data modules based on the identified orientation modules; and converting the data modules to data characters based on the identified data modules.
As a result of our research into solutions for the above described problems, we demonstrated the following.
First, the center point of a finder pattern can be found in the scanned image of a MaxiCode symbol by detecting, from among the detection patterns on scan lines through the scanned image, a detection pattern matching a specific reference pattern along a scan line through the finder pattern center point.
In addition, the process time needed to detect module dimensions and the location of the center point of the orientation modules in the scanned image of a MaxiCode symbol based on detected pixel data can be shortened compared with conventional methods by detecting all pixel data color patterns disposed a specific distance from the finder pattern center point and at a specific angle interval.
Furthermore, scanned images of MaxiCode symbols captured from an angle can be decoded as well as MaxiCode symbols captured from the front by computing an equation correlating an actual MaxiCode symbol finder pattern to the scanned image of a MaxiCode symbol captured from an angle similarly to an equation correlating a circle to an ellipse, and using this equation to correct the scanned image.
Furthermore, the orientation axes of a distorted scanned image can be corrected in the scanned image of a MaxiCode symbol by correcting the orientation axis angle so that the axis passes orientation module and data module center points based on the area of black module groups on an orientation axis passing the center of the finder pattern and an orientation module.
Furthermore, the position and shape of modules on the orientation axes of a distorted scanned image can be corrected based on the area of same-color module groups on a corrected orientation axis, and the positions of data modules between orientation axes can be corrected based on the position and shape of modules on the corrected orientation axes.
We also demonstrated that by detecting module position and shape information based on a corrected scanned image, the processing time of a decoding process for decoding a scanned image of a MaxiCode symbol can be shortened.
Yet further, we also demonstrated that by converting the detected data modules to a bit sequence, storing the converted data to a bit matrix table, and converting the bit data to codewords based on a two-dimensional codeword conversion table, the process time for converting data to data characters can be shortened compared with conventional methods.
Based on the above research results, the object of the invention is achieved with a method as claimed in claims 1, 7, 15, 23 and 30, an apparatus as claimed in claims 35, 44, 52 and 59, and a data storage medium as claimed in claim 64, respectively. Preferred embodiments of the invention are subject-matter of the dependent claims.
A two-dimensional bar code reading method according to one aspect of our invention comprises a data module search step for calculating position and shape information for all modules constituting a two-dimensional bar code symbol by calculating an orientation axis passing through an orientation module and finder pattern center point in a scanned image of a two-dimensional bar code symbol based on finder pattern position, orientation module position, and orientation module shape information in the scanned image.
In another aspect of the present invention the data module search step comprises the following steps:(a) an orientation axis module position calculating step for calculating, based on finder pattern position information and orientation module position information and shape information, position and shape information for a plurality of modules constituting a module group on said orientation axis; (b) an orientation axis data module bit pattern detecting step for detecting a bit pattern of said plural data modules on the orientation axis calculated by the orientation axis module position calculating step; (c) a between-orientation axis module position calculating step for calculating, based on the position and shape information of the plural modules of the module group on the orientation axis calculated by the orientation axis module position calculating step, position information for a plurality of modules constituting a module group between adjacent orientation axes; and (d) a between-orientation axis data module bit pattern detecting step for detecting the bit pattern of the plural data modules present between the orientation axes calculated by the between-orientation axis module position calculating step.
In another aspect of the present invention the orientation axis module position calculating step comprises the following steps: (a) an orientation axis angle correcting step for correcting the angle of the orientation axis so that the orientation axis passes the center points of the plural modules constituting a module group on the orientation axis; (b) an orientation axis actual module width correcting step for calculating position information for a plurality of actual modules present on an orientation axis corrected by the orientation axis angle correcting step and based on the calculated position information correcting the module width, which is shape information for the plural actual modules; (c) an orientation axis candidate module width correcting step for calculating position information for a plurality of candidate modules present on the orientation axis based on actual module position and shape information calculated by the orientation axis actual module width correcting step.
In another aspect of the present invention the orientation axis angle correcting step comprises the following steps: (a) a first corrected center point calculating step for calculating, based on a black module group area containing one or a plurality of contiguous black modules present on the orientation axis, a first corrected center point of a black module closest to the finder pattern in the black module group; (b) a second corrected center point calculating step for calculating a second corrected black module center point based on the area of a black module group comprising one or a plurality of contiguous black modules including the black module present on a neighboring reserve axis parallel to an orientation axis adjacent to the orientation axis and passing through the first corrected black module center point calculated by the first corrected center point calculating step; (c) a center point calculating step for calculating a black module center point based on the second corrected black module center point calculated by the second corrected center point calculating step, and the area of a black module group comprising one or a plurality of contiguous black modules including the black module present on an orientation reserve axis passing the finder pattern center point; and (d) an orientation axis correction angle calculating step for calculating a correction angle of an orientation axis passing the finder pattern center point and black module center point calculated by the center point calculating step.
In another aspect of the present invention the orientation axis actual module width correcting step comprises a step for calculating a center point and module width of actual modules constituting a same-color actual module group based on the area of a same-color actual module group comprising one or a plurality of contiguous same-color actual modules on the same orientation axis.
In another aspect of the present invention the orientation axis candidate module width correcting step comprises the following steps: (a) a reference orientation axis detecting step for detecting a reference orientation axis as the orientation axis having the least correction of all orientation axes; (b) a step for calculating center points and module widths for a plurality of candidate modules present on an orientation axis based on shape information for the black module farthest from the finder pattern on the reference orientation axis detected by the reference orientation axis detecting step; and (c) a step for calculating center points and module widths for a plurality of candidate modules present on an orientation axis other than the reference orientation axis based on actual module and candidate module positions on the reference orientation axis.
Another aspect of the present invention is a two-dimensional bar code reading method comprising a finder pattern search step for searching a scanned image of a two-dimensional bar code symbol for a scan line where a detected pattern in a specific scanning direction matches a specified reference pattern, detecting a finder pattern in the scanned two-dimensional bar code symbol image based on plural searched scan lines, and obtaining finder pattern position and shape information.
In another aspect of the present invention the finder pattern search step comprises steps for: (a) scanning a scanned image of a two-dimensional bar code symbol in a first scanning direction; (b) obtaining a first detection pattern by means of the first scanning step; (c) comparing the first detection pattern obtained by step (b) with a previously stored specific reference pattern; (d) defining said scan line as a first center line when step (c) determines the first detection pattern matches the specific reference pattern; (e) scanning the finder pattern in a second scanning direction that is different from the first scanning direction; (f) obtaining a second detection pattern by means of the second scanning step; (g) comparing the second detection pattern with the previously stored specific reference pattern; (h) defining said scan line as a second center line when step (g) determines the second detection pattern matches the specific reference pattern; and (i) setting the intersection of the first center line and the second center line as the center point of the finder pattern.
In another aspect of the present invention the finder pattern search step comprises steps for: (a) scanning a scanned image of a two-dimensional bar code symbol in a first scanning direction; (b) obtaining a first detection pattern by means of the first scanning step; (c) comparing the first detection pattern obtained by step (b) with a previously stored specific reference pattern; (d) setting said scan line as a first center line when step (c) determines the first detection pattern matches the specific reference pattern; (e) setting the midpoint between the two intersections of the first center line and outside circumference member of the finder pattern as a first center point; (f) repeating steps (b) to (e) after shifting parallel to the first center line to find plural first center points; (g) calculating a distribution of said plural first center points to the second scanning direction, which is different from the first scanning direction; (h) detecting a segment where the distribution to the second scanning direction is highest as a first line segment where the number of plural first center points in the second scanning direction is highest; (i) scanning in a second scanning direction on a line where the number of plural center points in the second scanning direction is highest;(j) obtaining a second detection pattern by means of the second scanning step; (k) comparing the second detection pattern with the previously stored specific reference pattern; (l) setting said scan line as a second center line when step (k) determines the second detection pattern matches the specific reference pattern; and (m) setting the midpoint between the two intersections of the second center line and outside circumference member of the finder pattern as a second center point; (n) repeating steps (j) to (m) after shifting parallel to the second center line to find plural second center points; (o) calculating a distribution of said plural second center points to the first scanning direction; (p) detecting a segment where the distribution to the first scanning direction is highest as a second line segment where the number of plural second center points in the first scanning direction is highest; and (q) setting the finder pattern center point to the intersection of the first line segment and second line segment.
In another aspect of the present invention the finder pattern search step comprises steps for: (a) scanning a scanned image of a two-dimensional bar code symbol in a first scanning direction; (b) obtaining a first detection pattern by means of the first scanning step; (c) comparing the first detection pattern obtained by step (b) with a previously stored specific reference pattern; (d) setting the midpoint between the two intersections of the scan line and outside circumference member of the finder pattern as a first center point when step (c) detects a match between the first detection pattern and the specific reference pattern; (e) finding plural first center points by shifting parallel to the first scanning direction and repeating steps (b) to (d); (f) scanning the finder pattern in a second scanning direction, which is different from the first scanning direction; (g) obtaining a second detection pattern by means of the second scanning step; (h) comparing the second detection pattern with the previously stored specific reference pattern; (i) setting the midpoint between the two intersections of the scan line and outside circumference member of the finder pattern as a second center point when step (h) detects a match between the second detection pattern and the specific reference pattern; (j) finding plural second center points by shifting parallel to the second scanning direction and repeating steps (g) to (i); (k) setting the finder pattern center point to the intersection of a line connecting the plural first center points and a line connecting the plural second center points.
In another aspect of the present invention the finder pattern search step comprises steps for: (a) scanning a scanned image of a two-dimensional bar code symbol in a first scanning direction; (b) obtaining a first detection pattern by means of the first scanning step; (c) comparing the first detection pattern obtained by step (b) with a previously stored specific reference pattern; (d) setting a first center line to the scan line from which the first detection pattern was obtained when step (c) detects a match between the first detection pattern and the specific reference pattern; (e) setting the midpoint between the two intersections of the first center line and outside circumference member of the finder pattern as a first center point; (f) scanning a second scanning direction different from the first scanning direction through the first center point; (g) obtaining a second detection pattern by means of the second scanning step; (h) comparing the second detection pattern with the previously stored specific reference pattern; (i) setting a second center line to the scan line from which the second detection pattern was obtained when step (h) detects a match between the second detection pattern and the specific reference pattern; (j) setting the midpoint between the two intersections of the second center line and outside circumference member of the finder pattern as a second center point; (k) calculating two intersections of the first center line and inside circumference member of the finder pattern, and two intersections of the second center line and inside circumference member of the finder pattern, from the midpoint between two intersections of the second center line and outside circumference member of the finder pattern; and (l) setting a barycenter determined from the two intersections of the first center line and inside circumference member of the finder pattern, and two intersections of the second center line and inside circumference member of the finder pattern, as the finder pattern center point.
In another aspect of the present invention the second scanning direction is orthogonal to the first scanning direction.
In another aspect of the present invention the finder pattern consists of plural concentric black circles and white circles, and comparison of the specific reference pattern with the first detection pattern and/or second detection pattern uses a ratio between an edge-to-edge distance between concentric black circles, and an edge-to-edge distance between concentric white circles.
In another aspect of the present invention the finder pattern search step comprises: (a) a first step for comparing a detected black and white pattern of a finder pattern obtained by scanning in the first scanning direction with a specific black and white reference pattern; (b) a second step for comparing a detected black and white pattern of a finder pattern obtained by scanning in the second scanning direction with a specific black and white reference pattern; and (c) obtaining center coordinates of the finder pattern by means of the first step and second step.
Another aspect of the present invention is a two-dimensional bar code reading method comprising an image correction step for calculating an equation indicating a correlation between a two-dimensional bar code symbol and a scanned image of the two-dimensional bar code symbol, and correcting the scanned image of the two-dimensional bar code symbol based on the equation.
In another aspect of the present invention, the image correction step generates a relation table achieving a specific correction precision by means of the equation indicating a correlation between a two-dimensional bar code symbol and a scanned image of the two-dimensional bar code symbol, and correcting the scanned image by means of the relation table.
In another aspect of the present invention the two-dimensional bar code symbol exists on a specific plane in the image correction step.
In another aspect of the present invention the scanned image is an image captured from an angle in the image correction step.
In another aspect of the present invention the equation indicating a correlation between a two-dimensional bar code symbol and a scanned image of the two-dimensional bar code symbol is a bias angle correction equation, and the scanned image is corrected by computing the bias angle correction equation, in the image correction step.
In another aspect of the present invention a circle in the scanned image is an element of the two-dimensional bar code symbol, or the shape of a deformed circle in the scanned image approximates an ellipse when a center of an element of the two-dimensional bar code symbol is on a specific circle.
In another aspect of the present invention a bias angle correction table is generated by means of a bias angle correction equation for an ellipse based on a specific correction angle division indicative of a correction precision.
In another aspect of the present invention a value of the bias angle correction equation at an angle equal to the correction angle division plus a specific offset angle is added to the bias angle correction table.
A two-dimensional bar code reading method according to another aspect of the present invention comprises an orientation module search step for finding in a scanned image of a two-dimensional bar code symbol plural pixel data groups whereof a black or white color pattern matches a specific color template pattern, the pixel data groups being disposed a specific distance from a specific point and at a specific angle interval, detecting a plurality of orientation modules constituting an orientation module group in the scanned image of a two-dimensional bar code symbol based on the found plural pixel data groups, and obtaining position and shape information for the plural orientation modules.
In another aspect of the present invention the specific color template pattern in the orientation module search step comprises a first color template pattern, a second color template pattern, and a third color template pattern.
In another aspect of the present invention the specific distance in the orientation module search step differs according to the first color template pattern, second color template pattern, and third color template pattern.
In another aspect of the present invention the specific distance is the product of module width and a specific value.
In another aspect of the present invention the module width is calculated based on shape information for the finder pattern in the scanned image of the two-dimensional bar code symbol, and a rate, said rate being a specific interval value present in a specific range.
In another aspect of the present invention wherein the orientation module search step comprises steps for: calculating one center point candidate for an orientation module located at said specific distance based on plural same-distance candidates for orientation module center points, said plural same-distance candidates being plural pixel data groups found based on said specific distance; and calculating an orientation module center point position from orientation module center point candidates at plural specific distances calculated at said rate.
In another aspect of the present invention the orientation module search step comprises a step for converting position information of a scanned image of a two-dimensional bar code symbol so that the center point of a specific orientation module is in a specific position.
A two-dimensional bar code reading method according to another aspect of the present invention comprises a data character conversion step for converting data module bit data to codewords, and converting the converted codewords to specific data characters, by correlating the positions of data modules constituting a data module group in the scanned image of a two-dimensional bar code symbol to specific codewords and specific bit data in the specific codewords based on a specific codeword conversion table.
In another aspect of the present invention data module positions in the data character conversion step are specified by a bit matrix table having elements in matrix BT(n,m).
In another aspect of the present invention said specific codeword is an i-th codeword, and said specific bit data in said specific codeword is a j-th bit of the i-th codeword, the specific codeword conversion table in the data character conversion step is a codeword matrix table of which values CT(n,m) satisfy the following equations i=[CT (n,m)/256] and j=CT (n,m)xe2x88x92i*256.
In each of the preceding aspects of the invention the two-dimensional bar code symbol encodes data by means of alternating black and white cells. In another aspect of the present invention the two-dimensional bar code symbol is a MaxiCode symbol.
One aspect of a two-dimensional bar code reading apparatus according to the present invention comprises a data module search unit for calculating position and shape information for all modules constituting a two-dimensional bar code symbol by calculating an orientation axis passing through an orientation module and finder pattern center point in a scanned image of a two-dimensional bar code symbol based on finder pattern position, orientation module position, and orientation module shape information in the scanned image.
In another aspect of a two-dimensional bar code reading apparatus wherein the data module search unit comprises: (a) an orientation axis module position calculating unit for calculating, based on finder pattern position information and orientation module position information and shape information, position and shape information for a plurality of modules constituting a module group on said orientation axis; (b) an orientation axis data module bit pattern detecting unit for detecting a bit pattern of said plural data modules on the orientation axis calculated by the orientation axis module position calculating unit; (c) a between-orientation axis module position calculating unit for calculating, based on the position and shape information of the plural modules of the module group on the orientation axis calculated by the orientation axis module position calculating unit, position information for a plurality of modules constituting a module group between adjacent orientation axes; and (d) a between-orientation axis data module bit pattern detecting unit for detecting the bit pattern of the plural data modules present between the orientation axes calculated by the between-orientation axis module position calculating unit.
In another aspect of a two-dimensional bar code reading apparatus the orientation axis module position calculating unit comprises: (a) an orientation axis angle correcting unit for correcting the angle of the orientation axis so that the orientation axis passes the center points of the plural modules constituting a module group on the orientation axis; (b) an orientation axis actual module width correcting unit for calculating position information for a plurality of actual modules present on an orientation axis corrected by the orientation axis angle correcting unit and based on the calculated position information correcting the module width, which is shape information for the plural actual modules; (c) an orientation axis candidate module width correcting unit for calculating position information for a plurality of candidate modules present on the orientation axis based on actual module position and shape information calculated by the orientation axis actual module width correcting unit.
In another aspect of a two-dimensional bar code reading apparatus the orientation axis angle correcting unit comprises: (a) a first corrected center point calculating unit for calculating, based on a black module group area containing one or a plurality of contiguous black modules present on the orientation axis, a first corrected center point of a black module closest to the finder pattern in the black module group; (b) a second corrected center point calculating unit for calculating a second corrected black module center point based on the area of a black module group comprising one or a plurality of contiguous black modules including the black module present on a neighboring reserve axis parallel to an orientation axis adjacent to the orientation axis and passing through the first corrected black module center point calculated by the first corrected center point calculating unit; (c) a center point calculating unit for calculating a black module center point based on the second corrected black module center point calculated by the second corrected center point calculating unit, and the area of a black module group comprising one or a plurality of contiguous black modules including the black module present on an orientation reserve axis passing the finder pattern center point; and (d) an orientation axis correction angle calculating unit for calculating a correction angle of an orientation axis passing the finder pattern center point and black module center point calculated by the center point calculating unit.
In another aspect of a two-dimensional bar code reading apparatus according to the present invention the orientation axis actual module width correcting unit comprises a calculating unit for calculating a center point and module width of actual modules constituting a same-color actual module group based on the area of a same-color actual module group comprising one or a plurality of contiguous same-color actual modules on the same orientation axis.
In another aspect of a two-dimensional bar code reading apparatus the orientation axis candidate module width correcting unit comprises: (a) a reference orientation axis detecting unit for detecting a reference orientation axis as the orientation axis having the least correction of all orientation axes; (b) a first computing unit for calculating center points and module widths for a plurality of candidate modules present on an orientation axis based on shape information for the black module farthest from the finder pattern on the reference orientation axis detected by the reference orientation axis detecting unit; and (c) a second computing unit for calculating center points and module widths for a plurality of candidate modules present on an orientation axis other than the reference orientation axis based on actual module and candidate module positions on the reference orientation axis.
Another aspect of a two-dimensional bar code reading apparatus according to the present invention comprises a finder pattern search unit for searching a scanned image of a two-dimensional bar code symbol for a scan line where a detected pattern in a specific scanning direction matches a specified reference pattern, detecting a finder pattern in the scanned two-dimensional bar code symbol image based on plural searched scan lines, and obtaining finder pattern position and shape information.
In another aspect of a two-dimensional bar code reading apparatus the finder pattern search unit comprises: (a) a scanning unit for scanning the finder pattern in plural directions; (b) a pattern detector for detecting a plurality of patterns by means of the scanning unit scanning plural directions; (c) memory for storing a specific template; (d) a comparison unit for comparing said plural patterns with each said specific template stored to memory; and (e) a decision unit for setting scan lines of the scanning unit as at least two center lines, and determining finder pattern center coordinates based on said two center lines.
In another aspect of a two-dimensional bar code reading apparatus the finder pattern search unit comprises: (a) a storage unit for prestoring a template determined by black and white pattern lengths; (b) a scanning unit for scanning the finder pattern in first and second scanning directions, and obtaining a black and white pattern; (c) a comparison unit for comparing black and white patterns of the finder pattern scanned by the scanning unit with said templates previously stored to the storage unit; (d) a decision unit for setting the first scan line scanned by the scanning unit as a first center line when the comparison unit determines the black and white pattern obtained by scanning in the first scanning direction matches the black and white pattern of the template, setting the second scan line scanned by the scanning unit as a second center line when the comparison unit determines the black and white pattern obtained by scanning in the second scanning direction matches the black and white pattern of the template, and setting the finder pattern center point to the intersection of the first center line and second center line.
Another aspect of a two-dimensional bar code reading apparatus according to the present invention comprises an image correction unit for calculating an equation indicating a correlation between a two-dimensional bar code symbol and a scanned image of the two-dimensional bar code symbol, and correcting the scanned image of the two-dimensional bar code symbol based on the equation.
In another aspect of a two-dimensional bar code reading apparatus according to the present invention the image correction unit generates a relation table achieving a specific correction precision by means of the equation indicating a correlation between a two-dimensional bar code symbol and a scanned image of the two-dimensional bar code symbol, and correcting the scanned image by means of the relation table.
In another aspect of a two-dimensional bar code reading apparatus according to the present invention the two-dimensional bar code symbol exists on a specific plane in the image correction unit.
In another aspect of a two-dimensional bar code reading apparatus according to the present invention the scanned image corrected by the image correction unit is an image captured from an angle.
In another aspect of a two-dimensional bar code reading apparatus the equation indicating a correlation between a two-dimensional bar code symbol and a scanned image of the two-dimensional bar code symbol is a bias angle correction equation, and the scanned image is corrected by computing the bias angle correction equation.
In another aspect of a two-dimensional bar code reading apparatus a circle in the scanned image is an element of the two-dimensional bar code symbol, or the shape of a deformed circle in the scanned image approximates an ellipse when a center of an element of the two-dimensional bar code symbol is on a specific circle.
In another aspect of a two-dimensional bar code reading apparatus a bias angle correction table is generated by means of a bias angle correction equation for an ellipse based on a specific correction angle division indicative of a correction precision.
In another aspect of a two-dimensional bar code reading apparatus according to the present invention a value of the bias angle correction equation at an angle equal to the correction angle division plus a specific offset angle is added to the bias angle correction table.
Another aspect of a two-dimensional bar code reading apparatus according to the present invention comprises an orientation module search unit for finding in a scanned image of a two-dimensional bar code symbol plural pixel data groups whereof a black or white color pattern matches a specific color template pattern, the pixel data groups being disposed a specific distance from a specific point and at a specific angle interval, detecting a plurality of orientation modules constituting an orientation module group in the scanned image of a two-dimensional bar code symbol based on the found plural pixel data groups, and obtaining position and shape information for the plural orientation modules.
In another aspect of a two-dimensional bar code reading apparatus according to the present invention the specific color template pattern in the orientation module search unit comprises a first color template pattern, a second color template pattern, and a third color template pattern.
In another aspect of a two-dimensional bar code reading apparatus according to the present invention the specific distance in the orientation module search unit differs according to the first color template pattern, second color template pattern, and third color template pattern.
In another aspect of a two-dimensional bar code reading apparatus according to the present invention the specific distance is the product of module width and a specific value.
In another aspect of a two-dimensional bar code reading apparatus according to the present invention the module width is calculated based on shape information for the finder pattern in the scanned image of the two-dimensional bar code symbol, and a rate, said rate being a specific interval value present in a specific range.
In another aspect of a two-dimensional bar code reading apparatus according to the present invention the orientation module search unit comprises: (a) a first calculating unit for calculating one center point candidate for an orientation module located at said specific distance based on plural same-distance candidates for orientation module center points, said plural same-distance candidates being plural pixel data groups found based on said specific distance; and (b) a second calculating unit for calculating an orientation module center point position from orientation module center point candidates at plural specific distances calculated at said rate.
In another aspect of a two-dimensional bar code reading apparatus according to the present invention the orientation module search unit comprises a conversion unit for converting position information of a scanned image of a two-dimensional bar code symbol so that the center point of a specific orientation module is in a specific position.
Another aspect of a two-dimensional bar code reading apparatus according to the present invention comprises a data character conversion unit for converting data module bit data to codewords, and converting the converted codewords to specific data characters, by correlating the positions of data modules constituting a data module group in the scanned image of a two-dimensional bar code symbol to specific codewords and specific bit data in the specific codewords based on a specific codeword conversion table.
In another aspect of a two-dimensional bar code reading apparatus according to the present invention data module positions in the data character conversion unit are specified by a bit matrix table with elements of matrix BT(n,m).
In another aspect of a two-dimensional bar code reading apparatus according to the present invention said specific codeword is an i-th codeword, and said specific bit data in said specific codeword is a j-th bit of the i-th codeword, the specific codeword conversion table in the data character conversion unit is a codeword matrix table of which values CT(n,m) satisfy the following equations:
i=[CT(n,m)/256]
j=CT(n,m)xe2x88x92i*256.
In another aspect of a two-dimensional bar code reading apparatus according to the present invention the two-dimensional bar code symbol encodes data by means of alternating black and white cells. Yet further preferably, the two-dimensional bar code symbol is a MaxiCode symbol.
One aspect of a data storage medium according to the present invention carries a program having steps of a two-dimensional bar code reading method according to the present invention.
Preferably, the data storage medium for recording a program according to the present invention is a Compact Disc, floppy disk, hard disk, magneto-optical disk, Digital Versatile Disc (DVD), magnetic tape, memory card or other computer readable medium.
Other objects and attainments together with a fuller understanding of the invention will become apparent and appreciated by referring to the following description of preferred embodiments taken in conjunction with the accompanying drawings.